// Time:  O(n)
// Space: O(1)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include "head/TreeNode.h"
#include <vector>
#include <cassert>
#include<iostream>
#include <queue>

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        postorderTraversalHelper(root, res);
        return res;
    }
private:
    void postorderTraversalHelper(TreeNode* root, std::vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        postorderTraversalHelper(root->left, res);
        postorderTraversalHelper(root->right, res);
        res.push_back(root->val);
    }
};

// Helper function to create a binary tree
TreeNode* createBinaryTree(const std::vector<int>& values) {
    if (values.empty()) return nullptr;
    TreeNode* root = new TreeNode(values[0]);
    std::queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (i < values.size()) {
        TreeNode* node = q.front();
        q.pop();
        if (values[i] != -1) {
            node->left = new TreeNode(values[i]);
            q.push(node->left);
        }
        i++;
        if (i < values.size() && values[i] != -1) {
            node->right = new TreeNode(values[i]);
            q.push(node->right);
        }
        i++;
    }
    return root;
}

// Test case
int main() {
    // Create a binary tree
    // Tree structure:
    //     1
    //      \
    //       2
    //      /
    //     3
    std::vector<int> values = {1, -1, 2, 3};
    TreeNode* root = createBinaryTree(values);

    // Create the Solution object
    Solution sol;

    // Perform postorder traversal
    std::vector<int> result = sol.postorderTraversal(root);

    // Expected postorder traversal: {3, 2, 1}
    std::vector<int> expected = {3, 2, 1};

    // Verify the result
    assert(result == expected);

    std::cout << "Test passed!" << std::endl;

    // Clean up the allocated memory
    // (In a real-world scenario, you would need to properly delete all nodes to avoid memory leaks)
    return 0;
}

